{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Segment Sum After Removals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #union-find #array #ordered-set #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #并查集 #数组 #有序集合 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumSegmentSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除操作后的最大子段和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code> 和&nbsp;<code>removeQueries</code>&nbsp;，两者长度都为&nbsp;<code>n</code>&nbsp;。对于第&nbsp;<code>i</code>&nbsp;个查询，<code>nums</code>&nbsp;中位于下标&nbsp;<code>removeQueries[i]</code>&nbsp;处的元素被删除，将 <code>nums</code>&nbsp;分割成更小的子段。</p>\n",
    "\n",
    "<p>一个 <strong>子段</strong>&nbsp;是 <code>nums</code>&nbsp;中连续 <strong>正</strong>&nbsp;整数形成的序列。<strong>子段和</strong>&nbsp;是子段中所有元素的和。</p>\n",
    "\n",
    "<p>请你返回一个长度为 <code>n</code>&nbsp;的整数数组<em>&nbsp;</em><code>answer</code>&nbsp;，其中<em>&nbsp;</em><code>answer[i]</code>是第&nbsp;<code>i</code>&nbsp;次删除操作以后的&nbsp;<strong>最大</strong>&nbsp;子段和。</p>\n",
    "\n",
    "<p><strong>注意：</strong>一个下标至多只会被删除一次。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,2,5,6,1], removeQueries = [0,3,2,4,1]\n",
    "<b>输出：</b>[14,7,2,2,0]\n",
    "<b>解释：</b>用 0 表示被删除的元素，答案如下所示：\n",
    "查询 1 ：删除第 0 个元素，nums 变成 [0,2,5,6,1] ，最大子段和为子段 [2,5,6,1] 的和 14 。\n",
    "查询 2 ：删除第 3 个元素，nums 变成 [0,2,5,0,1] ，最大子段和为子段 [2,5] 的和 7 。\n",
    "查询 3 ：删除第 2 个元素，nums 变成 [0,2,0,0,1] ，最大子段和为子段 [2] 的和 2 。\n",
    "查询 4 ：删除第 4 个元素，nums 变成 [0,2,0,0,0] ，最大子段和为子段 [2] 的和 2 。\n",
    "查询 5 ：删除第 1 个元素，nums 变成 [0,0,0,0,0] ，最大子段和为 0 ，因为没有任何子段存在。\n",
    "所以，我们返回 [14,7,2,2,0] 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [3,2,11,1], removeQueries = [3,2,1,0]\n",
    "<b>输出：</b>[16,5,3,0]\n",
    "<b>解释：</b>用 0 表示被删除的元素，答案如下所示：\n",
    "查询 1 ：删除第 3 个元素，nums 变成 [3,2,11,0] ，最大子段和为子段 [3,2,11] 的和 16 。\n",
    "查询 2 ：删除第 2 个元素，nums 变成 [3,2,0,0] ，最大子段和为子段 [3,2] 的和 5 。\n",
    "查询 3 ：删除第 1 个元素，nums 变成 [3,0,0,0] ，最大子段和为子段 [3] 的和 3 。\n",
    "查询 5 ：删除第 0 个元素，nums 变成 [0,0,0,0] ，最大子段和为 0 ，因为没有任何子段存在。\n",
    "所以，我们返回 [16,5,3,0] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length == removeQueries.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>0 &lt;= removeQueries[i] &lt; n</code></li>\n",
    "\t<li><code>removeQueries</code>&nbsp;中所有数字 <strong>互不相同</strong>&nbsp;。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-segment-sum-after-removals](https://leetcode.cn/problems/maximum-segment-sum-after-removals/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-segment-sum-after-removals](https://leetcode.cn/problems/maximum-segment-sum-after-removals/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,5,6,1]\\n[0,3,2,4,1]', '[3,2,11,1]\\n[3,2,1,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n, nums):\n",
    "        self.parent = [-1]*n\n",
    "        self.val = nums\n",
    "        self.maxnum = 0\n",
    "    \n",
    "    def union(self, index1, index2):\n",
    "        id1, v1 = self.find(index1)\n",
    "        id2, v2 = self.find(index2)\n",
    "        self.parent[id2] = id1\n",
    "        self.val[id2] = v1+v2\n",
    "        self.val[id1] = v1+v2\n",
    "\n",
    "    def find(self, index):\n",
    "        if self.parent[index] != index:\n",
    "            idx, vx = self.find(self.parent[index])\n",
    "            self.parent[index] = idx\n",
    "            self.val[index] = vx\n",
    "        return self.parent[index], self.val[index]\n",
    "    \n",
    "    def wake(self, index):\n",
    "        self.parent[index] = index\n",
    "        if index != 0 and self.parent[index-1] != -1:\n",
    "            self.union(index-1, index)\n",
    "        if index != len(self.parent)-1 and self.parent[index+1] != -1:\n",
    "            self.union(index, index+1)\n",
    "        a, b = self.find(index)\n",
    "        self.maxnum = max(self.maxnum, b)\n",
    "        return self.maxnum\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        union = UnionFind(len(nums), nums)\n",
    "        res = deque([0])\n",
    "        for q in removeQueries[:0:-1]:\n",
    "            res.appendleft(union.wake(q))\n",
    "        return list(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        sl1 = SortedList([s[-1]])  # 剩余的区间和排序数组\n",
    "        sl2 = SortedList([[0, n - 1]])  # 剩余的区间排序数组\n",
    "        ans = []\n",
    "        for x in removeQueries:\n",
    "            if len(sl2) == 0:\n",
    "                ans.append(0)\n",
    "                continue\n",
    "            p = sl2.bisect_left([x, n])\n",
    "            a, b = sl2[p - 1]\n",
    "            lp = s[b + 1] - s[a]\n",
    "            sl2.pop(p - 1)\n",
    "            sl1.remove(lp)\n",
    "            if x - a >= 1:\n",
    "                sl1.add(s[x] - s[a])\n",
    "                sl2.add([a, x - 1])\n",
    "            if b - x >= 1:\n",
    "                sl1.add(s[b + 1] - s[x + 1])\n",
    "                sl2.add([x + 1, b])\n",
    "            if len(sl1):\n",
    "                ans.append(sl1[-1])\n",
    "            else:\n",
    "                ans.append(0)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        from sortedcontainers import SortedList\n",
    "        L = len(nums)\n",
    "        holes = SortedList(range(-1, L+1))\n",
    "        accu = list(chain([0], accumulate(nums)))\n",
    "        res = [0] * L\n",
    "        for idx, rq in enumerate(reversed(removeQueries[1:]), 2):\n",
    "            off = holes.bisect_left(rq)\n",
    "            res[-idx] = max(res[-idx+1], accu[holes[off+1]] - accu[holes[off-1]+1])\n",
    "            holes.pop(off)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        dsu = Dsu(nums)\n",
    "        mx = 0\n",
    "        vis = set()\n",
    "        ans = []\n",
    "        for x in removeQueries[::-1]:\n",
    "            ans.append(mx)\n",
    "            if x + 1 in vis:\n",
    "                dsu.union(x, x + 1)\n",
    "            if x - 1 in vis:\n",
    "                dsu.union(x, x - 1)\n",
    "            pa = dsu.find(x)\n",
    "            vis.add(x)\n",
    "            mx = max(mx, dsu.s[pa])\n",
    "        return ans[::-1]\n",
    "\n",
    "class Dsu:\n",
    "    def __init__(self, nums):\n",
    "        n = len(nums)\n",
    "        self.pa = list(range(n))\n",
    "        self.s = [x for x in nums]\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.pa[x] != x:\n",
    "            self.pa[x] = self.find(self.pa[x])\n",
    "        return self.pa[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        px, py = self.find(x), self.find(y)\n",
    "        self.pa[px] = py\n",
    "        self.s[py] += self.s[px]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        fa = list(range(n + 1))\n",
    "        sz = [0] * (n + 1)\n",
    "        ans = [0] * (n + 1)\n",
    "\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            idx = removeQueries[i]\n",
    "            j = find(idx + 1)\n",
    "            fa[idx] = j\n",
    "            sz[j] += sz[idx] + nums[idx]\n",
    "            ans[i] = max(ans[i + 1], sz[j])\n",
    "\n",
    "        return ans[1:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        parents = list(range(n))\n",
    "        sizes = [0] * n\n",
    "        visited = [False] * n\n",
    "        def find(x):\n",
    "            if x != parents[x]:\n",
    "                parents[x] = find(parents[x])\n",
    "            return parents[x]\n",
    "\n",
    "        def union(u,v):\n",
    "            x , y = find(u) , find(v)\n",
    "            if x != y:\n",
    "                parents[x] = y\n",
    "                sizes[y] += sizes[x]\n",
    "\n",
    "        ans = [0]\n",
    "        max_val = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            i = removeQueries[i]\n",
    "            sizes[i] = nums[i]\n",
    "            visited[i] = True\n",
    "            if i - 1 >= 0 and visited[i-1]:\n",
    "                union(i,i-1)\n",
    "            if i + 1 < n and visited[i+1]:\n",
    "                union(i,i+1)\n",
    "            max_val = max(max_val,sizes[find(i)])\n",
    "            ans.append(max_val)\n",
    "        return ans[:-1][::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        from sortedcontainers import SortedList\n",
    "        L = len(nums)\n",
    "        holes = SortedList(range(-1, L+1))\n",
    "        parts = SortedList()\n",
    "        accu = list(chain([0], accumulate(nums)))\n",
    "        res = [0] * L\n",
    "        for idx, rq in enumerate(reversed(removeQueries[1:]), 2):\n",
    "            off = holes.bisect_left(rq)\n",
    "            if rq - holes[off-1] > 1:\n",
    "                x = accu[rq] - accu[holes[off-1]+1]\n",
    "                parts.remove(x)\n",
    "            if holes[off+1] - rq > 1:\n",
    "                x = accu[holes[off+1]] - accu[rq+1]\n",
    "                parts.remove(x)\n",
    "            parts.add(accu[holes[off+1]] - accu[holes[off-1]+1])\n",
    "            res[-idx] = parts[-1]\n",
    "            holes.pop(off)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        my_mat=[i for i in range(len(nums))]\n",
    "        def find(x):\n",
    "            if x!=my_mat[x]:\n",
    "                my_mat[x]=find(my_mat[x])\n",
    "            return my_mat[x]\n",
    "        def union(x,y):\n",
    "            my_mat[x]=find(my_mat[y])\n",
    "\n",
    "        my_list=SortedList([])\n",
    "        result=[0]\n",
    "        my_dict={}\n",
    "\n",
    "        for i in range(len(nums)-1,-0,-1):\n",
    "            now_index=removeQueries[i]\n",
    "            temp_sum=nums[now_index]\n",
    "            if now_index-1>=0:\n",
    "                if find(now_index-1) in my_dict:\n",
    "                    temp_sum+=my_dict[find(now_index-1)]\n",
    "                    my_list.remove(my_dict[find(now_index-1)])\n",
    "                    del my_dict[find(now_index-1)]\n",
    "                    union(now_index-1,now_index)\n",
    "\n",
    "            if now_index+1<len(nums):\n",
    "                if find(now_index+1) in my_dict:\n",
    "                    temp_sum+=my_dict[find(now_index+1)]\n",
    "                    my_list.remove(my_dict[find(now_index+1)])\n",
    "                    del my_dict[find(now_index+1)]\n",
    "                    union(now_index,now_index+1)\n",
    "\n",
    "            my_dict[find(now_index)]=temp_sum\n",
    "            my_list.add(temp_sum)\n",
    "            result.append(my_list[-1])\n",
    "\n",
    "        # result=result[0:len(result)]\n",
    "        return result[::-1]\n",
    "\n",
    "            \n",
    "             \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        fa = list(range(n + 1))\n",
    "        sz = [0] * (n + 1)\n",
    "        ans = [0] * n\n",
    "\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            idx = removeQueries[i]\n",
    "            j = find(idx + 1)\n",
    "            fa[idx] = j\n",
    "            sz[j] += sz[idx] + nums[idx]\n",
    "            ans[i - 1] = max(ans[i], sz[j])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        fa = list(range(n+1))\n",
    "        s = [0] * (n+1)\n",
    "\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        ans = [0] * (n)\n",
    "        for i in range(n-1,0,-1):\n",
    "            x = removeQueries[i]\n",
    "            to = find(x+1)\n",
    "            fa[x] = to\n",
    "            s[to] += s[x] + nums[x]\n",
    "            ans[i-1] = max(ans[i], s[to])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        fa=list(range(n+1))\n",
    "        s=[0]*(n+1)\n",
    "        def find(x):\n",
    "            if fa[x]!=x:\n",
    "                fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "        ans=[0]*n\n",
    "        for i in range(n-1,0,-1):\n",
    "            x=removeQueries[i]\n",
    "            to=find(x+1)\n",
    "            fa[x]=to\n",
    "            s[to]+=s[x]+nums[x]\n",
    "            ans[i-1]=max(ans[i],s[to])\n",
    "        return  ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        fa = list(range(n+1))\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        ans = [0] * n\n",
    "        s = [0] * (n+1)\n",
    "        for i in range(n-1, 0, -1):\n",
    "            x = removeQueries[i]\n",
    "            tb = find(x+1)\n",
    "            fa[x] = tb  \n",
    "            s[tb] += s[x] + nums[x]\n",
    "            ans[i-1] = max(ans[i], s[tb])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        fa = list(range(n + 1))\n",
    "        sum = [0] * (n + 1)\n",
    "        def find(x: int) -> int:\n",
    "            if x != fa[x]:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        ans = [0] * n\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            x = removeQueries[i]\n",
    "            to = find(x + 1)\n",
    "            fa[x] = to\n",
    "            sum[to] += sum[x] + nums[x]\n",
    "            ans[i - 1] = max(ans[i], sum[to])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        fa = list(range(n + 1))\n",
    "        sum = [0] * (n + 1)\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        ans = [0] * n\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            x = removeQueries[i]\n",
    "            to = find(x + 1)\n",
    "            fa[x] = to  # 合并 x 和 x+1\n",
    "            sum[to] += sum[x] + nums[x]\n",
    "            ans[i - 1] = max(ans[i], sum[to])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        fa = list(range(n + 1))\n",
    "        s = [0] * (n + 1)\n",
    "        ans = [0] * n\n",
    "        def find(x):\n",
    "            if fa[x] != x: fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            x = removeQueries[i]\n",
    "            to = find(x + 1)\n",
    "            fa[x] = to\n",
    "            s[to] += s[x] + nums[x]\n",
    "            ans[i - 1] = max(ans[i], s[to])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        p = list(range(n + 1))\n",
    "        s = [0] * (n + 1)\n",
    "        ans = [0] * n\n",
    "        def find(x):\n",
    "            if x != p[x]:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "        for i in range(n-1, 0, -1):\n",
    "            x = removeQueries[i]\n",
    "            to = find(x + 1)\n",
    "            p[x] = to\n",
    "            s[to] += s[x] + nums[x]\n",
    "            ans[i-1] = max(ans[i], s[to])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        from sortedcontainers import SortedList\n",
    "        n = len(nums)\n",
    "        h = [0] * (n + 3)\n",
    "        \n",
    "        def update(i, d):\n",
    "            while i <= n + 1:\n",
    "                h[i] += d\n",
    "                i += i & -i\n",
    "        def getsum(x):\n",
    "            s = 0\n",
    "            while x > 0:\n",
    "                s += h[x]\n",
    "                x -= x & -x\n",
    "            return s\n",
    "                \n",
    "        for i in range(n):\n",
    "            update(i + 1, nums[i])\n",
    "        # print(h)\n",
    "    \n",
    "        pos = SortedList([0, n + 1])\n",
    "        \n",
    "        total = SortedList([(0, n + 1)], key=lambda x: getsum(x[1]) - getsum(x[0] - 1))\n",
    "                          \n",
    "        ret = []\n",
    "        for p in removeQueries:\n",
    "            p += 1\n",
    "            idx = pos.bisect_left(p)\n",
    "            left, right = pos[idx - 1], pos[idx]\n",
    "            pos.add(p)\n",
    "            total.remove((left, right))\n",
    "            update(p, -nums[p-1])\n",
    "            if p - left > 1:\n",
    "                total.add((left, p))\n",
    "            if right - p > 1:\n",
    "                total.add((p, right))\n",
    "            if len(total):\n",
    "                left2, right2 = total[-1]\n",
    "                # print(left2, right2, p, total)\n",
    "                ret.append(getsum(right2) - getsum(left2-1))\n",
    "            else:\n",
    "                ret.append(0)\n",
    "        return ret\n",
    "            \n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        # bingchaji\n",
    "        f = list(range(n+1))\n",
    "        sum = [0] * (n+1)\n",
    "        ans = [0] * n \n",
    "\n",
    "        def find(x) :\n",
    "            if x != f[x]:\n",
    "                f[x] = find(f[x])\n",
    "            return f[x]\n",
    "        \n",
    "        for i in range (n-1,0,-1):\n",
    "            x = removeQueries[i]\n",
    "            to = find(x+1)\n",
    "            f[x] = to\n",
    "            sum[to] += sum[x] + nums[x]\n",
    "            ans[i-1] = max(ans[i],sum[to])\n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        \n",
    "        pa = list(range(n))\n",
    "        we = [-1] * n\n",
    "        def find(x):\n",
    "            if pa[x] != x:\n",
    "                pa[x] = find(pa[x])\n",
    "            return pa[x]\n",
    "        def union(i,j):\n",
    "            x,y = map(find,[i,j])\n",
    "            if x == y: return\n",
    "            if we[x] < we[y]: x,y = y,x\n",
    "            pa[y] = x\n",
    "            we[x] += we[y]\n",
    "            we[y] = 0\n",
    "        \n",
    "        ans = [0]\n",
    "        max_val = 0\n",
    "        for i in removeQueries[n-1:0:-1]:\n",
    "            we[i] = nums[i]\n",
    "            if i > 0 and we[i-1] != -1: union(i,i-1)\n",
    "            if i < n-1 and we[i+1] != -1: union(i,i+1)\n",
    "            max_val = max(max_val,we[find(i)])\n",
    "            ans.append(max_val)\n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\r\n",
    "删除改为增加，动态维护每个子段的元素和，高效地合并两个子段。\r\n",
    "'''\r\n",
    "class Solution:\r\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\r\n",
    "        n = len(nums)\r\n",
    "        fa = [i for i in range(n+1)]\r\n",
    "        sum = [0] * (n + 1)\r\n",
    "        def find(x: int) -> int:\r\n",
    "            if fa[x] != x:\r\n",
    "                fa[x] = find(fa[x])\r\n",
    "            return fa[x]\r\n",
    "        ans = [0] * n\r\n",
    "        for i in range(n - 1, 0, -1):\r\n",
    "            x = removeQueries[i]\r\n",
    "            to = find(x + 1)\r\n",
    "            fa[x] = to  # 合并 x 和 x+1\r\n",
    "            sum[to] += sum[x] + nums[x]\r\n",
    "            ans[i - 1] = max(ans[i], sum[to])\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        \n",
    "        pa = list(range(n))\n",
    "        we = [0] * n\n",
    "        def find(x):\n",
    "            if pa[x] != x:\n",
    "                pa[x] = find(pa[x])\n",
    "            return pa[x]\n",
    "        def union(i,j):\n",
    "            x,y = map(find,[i,j])\n",
    "            if x == y: return\n",
    "            if we[x] < we[y]: x,y = y,x\n",
    "            pa[y] = x\n",
    "            we[x] += we[y]\n",
    "        \n",
    "        ans = [0]\n",
    "        max_val = 0\n",
    "        for i in removeQueries[n-1:0:-1]:\n",
    "            we[i] = nums[i]\n",
    "            if i > 0 and we[i-1]: union(i,i-1)\n",
    "            if i < n-1 and we[i+1]: union(i,i+1)\n",
    "            max_val = max(max_val,we[find(i)])\n",
    "            ans.append(max_val)\n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], rq: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        fa = list(range(n + 1))\n",
    "        sm = [0] * (n + 1)\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        mx=0\n",
    "        ans=[0]*n\n",
    "\n",
    "        for i in range(n-1,-1,-1):\n",
    "            ans[i]=mx\n",
    "            #merge(rq[i],rq[i]+1)\n",
    "            j=find(rq[i]+1)\n",
    "            fa[rq[i]]=j  \n",
    "            sm[j]+=sm[rq[i]]+nums[rq[i]]\n",
    "            mx=max(mx,sm[j])\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        parent = {i : i for i in range(n)}\n",
    "        size = [0] * n \n",
    "        def find(node):\n",
    "            path = []\n",
    "            while node != parent[node]:\n",
    "                path.append(node)\n",
    "                node = parent[node]\n",
    "            for p in path:\n",
    "                parent[p] = node \n",
    "            return node \n",
    "        \n",
    "        def union(n1, n2):\n",
    "            p1 = find(n1)\n",
    "            p2 = find(n2)\n",
    "            if p1 != p2:\n",
    "                if p1 < p2:\n",
    "                    parent[p1] = p2 \n",
    "                    size[p2] += size[p1]\n",
    "                else:\n",
    "                    parent[p2] = p1 \n",
    "                    size[p1] += size[p2]\n",
    "            \n",
    "        curMax = 0\n",
    "        res = []\n",
    "        for q in removeQueries[::-1]:\n",
    "            res.append(curMax)\n",
    "            size[q] = nums[q]\n",
    "            if q < n - 1 and size[q + 1] > 0:\n",
    "                union(q, q + 1)\n",
    "            if q > 0 and size[q - 1] > 0:\n",
    "                union(q - 1, q)\n",
    "            curMax = max(curMax, size[q], size[find(q)])\n",
    "        return res[::-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [0] * n\n",
    "        ufd = UnionFind(n)\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            c = removeQueries[i]\n",
    "            num = nums[c]\n",
    "            ufd.value[c] = num\n",
    "            ufd.mx = max(num, ufd.mx)\n",
    "            if c - 1 >= 0 and c - 1 in ufd.value:\n",
    "                ufd.union(c - 1, c)\n",
    "            if c + 1 < n and c + 1 in ufd.value:\n",
    "                ufd.union(c + 1, c)\n",
    "            ans[i - 1] = ufd.mx\n",
    "        return ans\n",
    "\n",
    "class UnionFind:\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.mx = 0\n",
    "        self.value = defaultdict(int)\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        rx, ry = self.find(x), self.find(y)\n",
    "        if rx == ry:\n",
    "            return \n",
    "        \n",
    "        if self.size[ry] > self.size[rx]:\n",
    "            rx, ry = ry, rx\n",
    "        self.parent[ry] = rx\n",
    "        self.size[rx] += self.size[ry]\n",
    "        self.value[rx] += self.value[ry]\n",
    "        self.mx = max(self.mx, self.value[rx])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        # o(nlogn) 逆向思考 变成并查集\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        fx = list(range(n+1))\n",
    "        def find(x):\n",
    "            if fx[x] != x:\n",
    "                fx[x] = find(fx[x])\n",
    "            return fx[x]\n",
    "        #往前合并，但是记得\n",
    "        def union(x,y):\n",
    "            fx[find(x)] = find(y)\n",
    "        sz = [0] * (n+1)\n",
    "        m = 0\n",
    "        new_num = []\n",
    "        for i in removeQueries:\n",
    "            new_num.append(nums[i])\n",
    "        for val,loc in list(zip(new_num,removeQueries))[::-1]:\n",
    "            floc = find(loc+1)\n",
    "            fx[loc] = floc\n",
    "            sz[floc] += sz[loc] + val \n",
    "            res.append(m)\n",
    "            m = max(m, sz[fx[floc]])\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        from sortedcontainers import SortedList\n",
    "        spans = SortedList([[-1, len(nums)]])\n",
    "        res = [0]*len(removeQueries)\n",
    "        accus = list(accumulate(chain([0], nums)))\n",
    "        h = [(-accus[-1], -1, len(nums))]\n",
    "        for i, off in enumerate(removeQueries):\n",
    "            spanOff = spans.bisect_right([off, 0]) - 1\n",
    "            span = spans[spanOff] \n",
    "            l, r = span\n",
    "            spanSum = accus[r] - accus[l+1]\n",
    "            spans.pop(spanOff)\n",
    "            if off - l > 1:\n",
    "                spans.add([l, off])\n",
    "                leftSum = accus[off] - accus[l+1]\n",
    "                heappush(h, (-leftSum, l, off))\n",
    "            if r - off > 1:\n",
    "                spans.add([off, r])\n",
    "                rightSum = accus[r] - accus[off+1]\n",
    "                heappush(h, (-rightSum, off, r))\n",
    "            while h:\n",
    "                negSum, l, r = h[0]\n",
    "                spanOff = spans.bisect_left([l, 0])\n",
    "                if spanOff < len(spans):\n",
    "                    sl, sr = spans[spanOff]\n",
    "                    if sl == l and sr == r:\n",
    "                        res[i] = -negSum\n",
    "                        break\n",
    "                heappop(h)\n",
    "        return res\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        pa = list(range(n+1))\n",
    "        we = [0] * (n+1)\n",
    "        def find(x):\n",
    "            if pa[x] != x: pa[x] = find(pa[x])\n",
    "            return pa[x]\n",
    "        ans = [0]\n",
    "        max_val = 0\n",
    "        for i in removeQueries[n-1:0:-1]:\n",
    "            j = find(i)\n",
    "            we[j] += we[i+1] + nums[i]\n",
    "            pa[i+1] = j\n",
    "            ans.append(max(ans[-1],we[j]))\n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "        :param nums:\n",
    "        :param removeQueries:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        dp = {}\n",
    "        dp[-1] = 0\n",
    "        cache = 0\n",
    "        for k, v in enumerate(nums):\n",
    "            cache += v\n",
    "            dp[k] = cache\n",
    "        sd1 = SortedList(key=lambda x: -x[1])\n",
    "        sd1.add(((0, len(nums) - 1), cache))\n",
    "        sd2 = SortedList(key=lambda x: x[0][1])\n",
    "        sd2.add(((0, len(nums) - 1), cache))\n",
    "        ret = []\n",
    "        for k, v in enumerate(removeQueries):\n",
    "            idx1 = sd2.bisect_left(((v, v), 0))\n",
    "            tocheck = sd2[idx1]\n",
    "            i = tocheck[0]\n",
    "            if i[0] <= v <= i[1]:\n",
    "                sd1.remove(tocheck)\n",
    "                sd2.remove(tocheck)\n",
    "                if i[0] == i[1]:\n",
    "                    if len(sd1) > 0:\n",
    "                        ret.append(sd1[0][1])\n",
    "                    else:\n",
    "                        ret.append(0)\n",
    "                else:\n",
    "                    if i[0] == v:\n",
    "                        delta1 = dp[i[1]] - dp[v]\n",
    "                        sd1.add(((v + 1, i[1]), delta1))\n",
    "                        sd2.add(((v + 1, i[1]), delta1))\n",
    "                    elif i[1] == v:\n",
    "                        delta1 = dp[v - 1] - dp[i[0] - 1]\n",
    "                        sd1.add(((i[0], v - 1), delta1))\n",
    "                        sd2.add(((i[0], v - 1), delta1))\n",
    "                    else:\n",
    "                        delta1 = dp[i[1]] - dp[v]\n",
    "                        delta2 = dp[v - 1] - dp[i[0] - 1]\n",
    "                        sd1.add(((v + 1, i[1]), delta1))\n",
    "                        sd2.add(((v + 1, i[1]), delta1))\n",
    "                        sd1.add(((i[0], v - 1), delta2))\n",
    "                        sd2.add(((i[0], v - 1), delta2))\n",
    "                    ret.append(sd1[0][1])\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        pa = list(range(n+1))\n",
    "        we = [0] * (n+1)\n",
    "        def find(x):\n",
    "            if pa[x] != x: pa[x] = find(pa[x])\n",
    "            return pa[x]\n",
    "        ans = [0]\n",
    "        for i in removeQueries[n-1:0:-1]:\n",
    "            j = find(i)\n",
    "            we[j] += we[i+1] + nums[i]\n",
    "            pa[i+1] = j\n",
    "            ans.append(max(ans[-1],we[j]))\n",
    "        return ans[::-1]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
